Rust で Bresenhamの線分描画アルゴリズムを用いて 三角形 を書く
https://scrapbox.io/files/66f783fa6ba7d1001c77d232.png
方針
1. 3頂点を$ y座標値に基づいてソートする
2. $ y方向を線形走査する形で、三角形内部を塗りつぶす
ある$ y = y_0における三角形の端点がどこにあるかを調べたい https://scrapbox.io/files/66ee77e44bc5c1001cea3093.png
ある2点を指定したら、その2点を結ぶ長さ1の線分上の点を列挙するiteratorを実装する。
始点$ p_1から終点$ p_2へを辿るイテレータであること
より厳密には
1. 一回だけnext()を呼んだ時、$ p_1の座標を返す。
2. 十分な回数next()を呼んだ時、$ p_2を得ることができる。
3. next() の戻り値が$ pであったときに、再度next()を呼び出すと$ p'が得られる。
ただし、
4. 線分の太さが$ 1である。
厳密には、次のいずれかが成立する。
任意の$ yに対して、ある$ xが一つだけ存在して、$ (x, y)をnext()が出力する。
任意の$ xに対して、ある$ yが一つだけ存在して、$ (x, y)をnext()が出力する。
ただし、$ x, yの値域はそれぞれ線分$ p_1, p_2が$ x座標において渡る区間、$ y座標において渡る区間に対応する。
p1からp2に辿るようにイテレータを修正したappbird.icon
実装
現在地点currentと、次に行く地点nextを保持
nextがメソッドを表す時とフィールドを表す時があることに注意（命名が悪い）
next()関数は、
1. currentを戻り値とする。
2. currentをnextで上書きする。（current == next）
3. nextを進める。
累積誤差self.errに基づいて、self.next.xを更新する。
というわけで、これだけで線分が書けるようになったappbird.icon
code:rs
for p in BresenhamLine::trace(p1, p2){
self.draw_pixel(p.x as usize, p.y as usize, color)
}
AC.icon 三角形の端点を得る
https://scrapbox.io/files/66ee77e44bc5c1001cea3093.png
こういう感じにアルゴリズムが進んでいる時に、各$ yごとに塗る領域を表す$ xの区間を得ることで、三角形を表すのに塗るべき領域を求めたい。
図には三色塗られている
薄い橙 ... 塗るべき領域
中ぐらいの橙 ... Bresenhamのアルゴリズムが進んでいる時に線分として塗られる部分
濃い橙 ... 実際の端点
要約
あるy値に対して、そのy座標におけて三角形の塗るべき区間は
イテレータ(1)に対してそのy値に初めて入った時の画素p1, 次のステップでy値が加算される時の画素p1_prime
イテレータ(2)に対してそのy値に初めて入った時の画素p2, 次のステップでy値が加算される時の画素p2_prime
それらのx値の区間[p1.x, p2.x]と区間[p1_prime.x, p2_prime.x]の合併区間とする。
導出
中ぐらいの橙の画素は青矢印のようにBresenham iteratorを2つ走らせれば辿ることができる
https://scrapbox.io/files/66ee78dd55c717001c9016f4.png
左のイテレータを(1), 右のイテレータを(2)としよう
ただ、本当に欲しいのはその中でも濃い橙のところ。
どうやって得る？
そうでない場合は....まず、$ yの増えるステップの直前で辿る画素が端な場合を考えよう。
描く対象の線分に対して、ブレゼンハムの累積誤差の増分$ \Delta eは一定。
除算を使って、現在の累積誤差に対して後どれだけステップを進めれば良いかを求めれば良い。
$ y = y_0における$ yの端点位置$ x_0を得るために以下を繰り返す。
前提: イテレータの辿る点の$ y座標が$ y_0になる直前までイテレータが到達している
1. 一回イテレータを進める（この段階で、イテレータが辿る点の$ y座標が$ y_0になる）
この地点で、
2. イテレータに保存された累積誤差$ eを参照して、後何回イテレータを進めれば直前までいけるかを除算で求める
$ (e - 1) \div \Delta e
$ \Delta e | eであったとき、$ e / \Delta eより$ 1小さい値になる。
$ \Delta e \not | eであったとき、$ \lfloor e / \Delta e \rfloorと同じ値になる。
3. その分だけイテレータを進める（ように内部パラメータを書き換える）
ここは工夫すれば$ O(1)で計算できる。
こうすることで、橙だけを辿ることができる。
しかし、実際には、次のように$ yの増えるステップの直前の画素が端にならない場合もある。
https://scrapbox.io/files/66ee8900dc2206001d5f082a.png
これの各ケースに対応させて端を求めるのを書くのは場合わけがしんどいので、楽する。
まず、次のように三角形の辺を辿る二つのイテレータを用意する。
https://scrapbox.io/files/66ee8a7a946564001cce5d02.png
(1)のイテレータを$ i_1、(2)のイテレータを$ i_2と呼ぶ。
(1)は一番下の頂点から一番上の頂点までを一つの線分で辿る
(2)は一番下の頂点から中間の頂点を辿った後、までを辿る
三角形が渡っている$ yの区間$ y_{min}, \cdots, y_{max}を順々に辿っていくとして
各々の$ y_0 \in \{y_{min}, \cdots, y_{max}\}について
前提: イテレータの辿る点の$ y座標が$ y_0になる直前までイテレータが到達している
1. 一回$ i_1, y_2のイテレータを進める（この段階で、イテレータが辿る点の$ y座標が$ y_0になる）
この地点で$ i_1, i_2が返した点の$ x座標を$ x_1, x_2としよう。
これの閉区間$ \lbrack x_1, x_2\rbrackを考えておく。 この閉区間は描画すべき$ xの区間に含まれている。
2. イテレータの辿る点の$ y座標が$ y_0 + 1に到達する直前までイテレータ$ i_1, i_2を送る。
この時もまだイテレータが
3. その地点でのイテレータ$ i_1, i_2のいる点の$ x座標を$ x_1', x_2'として、その閉区間$ \lbrack x_1', x_2'\rbrackも考えておく。
4. $ \lbrack x_1, x_2\rbrack \cup \lbrack x_1', x_2'\rbrackは$ y = y_0において塗るべき$ xの区間を示している（はず）
1.か3.かのどっちかの地点で、それぞれのイテレータが端にいることを利用している。
証明はしてないけど多分正しいと思うappbird.icon
https://scrapbox.io/files/660b891844029500264dcdb6.png
$ y値が増える直前までイテレータを送るには？
イテレータにメソッドskip_to_next_y()を実装する
戻り値：y値が増える直前におけるイテレータの点座標
実行後要件
これを実行し始めた地点での点のy座標と、同じy座標にcurrentが存在するが
nextのy値はそれより1進んでいる状態になる。
i) 実行後要件がすでに満たされていた場合はself.currentを返す。
ii) そうでなかった場合は、self.nextをy値が増える直前まで
累積誤差self.errがあと何回増えれば0を超えるかを考える。
self.errがself.nextの点に関するものであることに注意。
self.currentと勘違いしてプログラムを進めるとバグる
その回数分だけxを進めれば良い。
yを進めることは考えなくて良い。
$ (e - 1) \div \Delta e回分
$ \Delta e | eであったとき、$ e / \Delta eより$ 1小さい値になる。
$ \Delta e \not | eであったとき、$ \lfloor e / \Delta e \rfloorと同じ値になる。
その上で、self.currentをself.nextで上書きした上で、一回分self.next()を進める。
こうすることで、self.currentにはyが増加する直前の点、self.nextにはyが増加した後の点が格納できるappbird.icon
code:rs
/** y値が更新される直前までイテレータを飛ばす。 */
pub fn skip_to_next_y(&mut self) -> Option<Point2> {
// Y軸に沿っていた場合は、その地点がすでにy値が更新される直前の点である。
if !self.along_x_axis || self.next.y != self.current.y {
return self.at();
}
// X軸に沿っていた場合、イテレータを1回進めてy値が1上昇するとは限らないため
// 次にy値が上がるまでイテレータを複数回進める（のと等価なO(1)動作を行う。）
let left_step = i32::abs(self.p2.x - self.current.x);
let dy = self.offset.y;
// self.errが0より大きくなる直前までxを進める。まず、進めるべき回数を求める。
let err_1step = 2 * i32::abs(dy);
let step_x = min((self.err.abs()) / err_1step, left_step);
// その後、その回数分だけ進めた（ことにする）
self.next.x += self.x_direction * step_x;
self.err += err_1step * step_x;
self.current = self.next.clone();
self.next()
}
そしてそのイテレータを使って実装
各yに対して、一回next()を進めて、その後skip_to_next_y()でy値が更新される直前まで行く。
それらの時に取れた座標値を元に、塗るべきxの区間を定める。
code:rs
pub fn draw_triangle(
&mut self,
color: &Color
) {
// y基準でソート
// 三角形の輪郭を求める
let mut iter1 = [
BresenhamLine::trace(bottom, middle),
BresenhamLine::trace(middle, top),
];
let mut iter1_idx = 0;
let mut iter2 = BresenhamLine::trace(bottom, top);
for y in bottom.y .. top.y{
// 次のイテレータのポイントを見出す
let p1 =
if let Some(x) = iter1iter1_idx.next() { x } else { assert!(iter1_idx == 0);
iter1_idx += 1;
};
let p2 =
if let Some(x) = iter2.next() { x } else { break; };
// それぞれのイテレータの辿っている点のy座標がyに達するまでスキップする
let edge1 = iter1iter1_idx.skip_to_next_y().unwrap(); let edge2 = iter2.skip_to_next_y().unwrap();
assert_eq!(p1.y, y);
assert_eq!(p1.y, edge1.y);
assert_eq!(p2.y, y);
assert_eq!(p2.y, edge2.y);
let before = ClosedInterval::between(p1.x, p2.x);
let after = ClosedInterval::between(edge1.x, edge2.x);
let draw_interval = before.or(after);
for x in draw_interval {
self.draw_pixel(&Point2::new(x, y), color);
}
}
}
というわけで、得られたのがこちらappbird.icon
いい感じに描けている
https://scrapbox.io/files/66f783fa6ba7d1001c77d232.png
code:rs
pub fn triangle(camera:&mut Camera, canvas:&mut Canvas) -> Throwable<()> {
let points = [
Vec4::new(0.5, 0.2, 0., 0.),
Vec4::new(-0.8, -0.5, 0., 0.),
Vec4::new(-0.5, 0.5, 0., 0.)
];
let points:Vec<Vec4Project> = points.iter().map(|e| Vec4Project(e.clone())).collect();
let white = Color::new(1., 1., 1., 1.);
let red = Color::new(1., 0., 0., 1.);
for point in &points {
camera.draw_point(canvas, &point, &red);
}
camera.draw_triangle(
canvas,
&points0, &points1, &points2, &white
);
Ok(())
}